package com.cg.leetcode;

import org.junit.Test;

import java.util.*;

/**
 * 113.路径总和 II
 *
 * @program: LeetCode->LeetCode_113
 * @author: cg
 * @create: 2022-04-25 08:55
 **/
public class LeetCode_113 {

    @Test
    public void test113() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);

        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);
        System.out.println(pathSum(root, 22));
    }

    /**
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     * <p>
     * 示例 1：
     * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
     * 输出：[[5,4,11,2],[5,8,4,5]]
     * <p>
     * 示例 2：
     * 输入：root = [1,2,3], targetSum = 5
     * 输出：[]
     * <p>
     * 示例 3：
     * 输入：root = [1,2], targetSum = 0
     * 输出：[]
     * <p>
     * 提示：
     * 树中节点总数在范围 [0, 5000] 内
     * -1000 <= Node.val <= 1000
     * -1000 <= targetSum <= 1000
     *
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> path = new ArrayList<>();
        dfs(root, targetSum, res, path);
        return res;
    }

    private void dfs(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        targetSum -= root.val;

        if (root.left == null && root.right == null) {
            if (targetSum == 0) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        if (root.left != null) {
            dfs(root.left, targetSum, res, path);
            // 回溯
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            dfs(root.right, targetSum, res, path);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}
